1. Field of the Invention
The present invention relates to a packet classification search device and method for performing packet transmission processing in a packet transmission device such as an IP (Internet Protocol) router or the like, which classify what type of processing to perform upon packets such as IP packets from information such as header information included in these packets; and in particular relates to a search technique for tables or the like which are searched when determining upon the processing to apply to the packets.
2. Description of the Related Art
In the past, in a packet transmission device such as an IP router or the like, a routing table has been searched based upon destination addresses which are included in the packet headers to determine the next route. The relationship between the destination address and the next route is stored in the routing table. With conventional networks such as the Internet, only simple transmission processing has been performed in this manner, using only the destination address. This point will now be explained in the following by giving a concrete structural example.
FIG. 19 shows how an IP packet or the like carrying data is transmitted, and in this figure the reference symbols 2-1, 2-2, and 2-3 denote networks which are connected to a router 1, while 3-1, 3-2, and 3-3 denote signal lines which connect the router 1 and the networks 2-1, 2-2, and 2-3, and the reference symbol 4 denotes an IP packet. Furthermore, the reference symbols 5-1, 5-2, . . . 5-A are terminals which are present in the network 2-1, the reference symbols 6-1, 6-2, . . . 6-B are terminals which are present in the network 2-2, and the reference symbols 7-1, 7-2 . . . 7-C are terminals which are present in the network 2-3 (where A, B, and C are any integers greater than or equal to 2).
Furthermore, as is customary, the network addresses in FIG. 19 are separated by xe2x80x9c.xe2x80x9d characters into groups of 8 bits each of which is expressed in decimal, and the number after the xe2x80x9c/xe2x80x9d shows, in the IP address, how many bits from the most significant bit is to be taken as the network address.
The IP packet 4 contains the IP address of the terminal which is scheduled as its destination, and data. In the past, the router 1 has only searched for the destination IP address contained in the IP header of the IP packet 4, and has decided based thereupon from which signal line to forward the IP packet.
However, in recent years, along with the expansion of the Internet, the conventional type of simple transmission processing using only the destination IP address has proved to be insufficient, and a higher degree of transmission control has become necessary. For example, in order to provide diversification of service upon a data network and in order to address problems of security, attention has focused upon packet classification which performs various procedures for QoS (Quality of Service) control or policy control by searching not only the destination IP addresses which are included in the IP headers of the packets, but also the source IP addresses or other information (such as the TCP (Transmission Control Protocol)/UDP (User Datagram Protocol), port number, or the like), and furthermore by searching not only the IP headers but also other header information within the packets, and by identifying the packets in more detail. Thus by packet classification is meant performing different processing for each flow of IP packets, in order to implement IP value added services such as QoS, VPN (Virtual Private Network), firewalls and the like.
The router classifies the packets in detail by packet classification, and may implement value added services by forwarding packets while allocating priority to them according to contract, or may implement discarding of packets from malicious users. In more concrete terms, it is possible to implement QoS control by performing priority control of the packets based upon the source addresses of their users and their TCP/UDP port numbers, in order to enhance the QoS of packet transmission of specified applications from specified users. Furthermore, if specified applications are to be prevented from communication and their packets are to be discarded, it is possible to implement policy control by filtering so as not to transmit packets which have the TCP/UDP port numbers which are allocated to these applications. A rule table (also termed a xe2x80x9cpolicy tablexe2x80x9d) which will be described hereinafter is searched for rules required for this type of procedure.
Six representative ones of the various fields (field information in packet headers) for classifying packets are: destination address (DA), source address (SA), protocol identifier (PID), destination port number (DP), source port number (SP), and differentiated service code point (DSCP). And the combinations of information corresponding to these fields and actions with regard to the packets (forward at high priority, forward at medium priority, forward at low priority, denying etc.) are hereinafter termed rules (or policies), and these rules are mainly determined and set into the router by the network administrator.
FIG. 20 shows an example of rules for packet classification based upon the network structure of FIG. 19, and in this figure the reference symbol 10 denotes the rule table, while the reference symbols 11, 12, 13, and 14 are rules. The rule table 10 is searched with a plurality of fields in the packet header as search keys, and it is used for determining the action to be applied to these packets. If these rules 11 through 14 are set into the router 1 of FIG. 19, when for example a packet using the UDP protocol and whose destination port number is 100 is forwarded from the terminal 5-1 of the network 2-1 to the terminal 7-1 of the network 2-3, since all the fields (the destination address, the source address, the protocol, and the destination port number) of this packet agree with rule 11 (however, the xe2x80x9cdestination port numberxe2x80x9d of rule 11 is xe2x80x9cdon""t carexe2x80x9d and thus matches anything), therefore the router 1 performs the action described by the xe2x80x9cActionxe2x80x9d of rule 11 upon this packet. In other words, the router 1 forwards this packet with high priority.
FIG. 21 shows an example of the structure of an IP packet and the main header information. Although this IP packet is principally composed of a local network header 21, an IP header 22, an upper-layer header 23 (in the figure termed a TCP header), user data (in the figure termed TCP data), and a local network trailer 25, a plurality of fields which are present in each header have the possibility of being used in packet classification.
Along with increase of the degree of attention given to packet classification, the requirement for more detailed classification of the packets has increased, and the number of fields in the header which are to be searched has also increased. Furthermore, in recent years, with the commencement of the introduction of the new IPv6 protocol, the destination IP address and the source IP address are both 128 bits long, so that the number of bits has greatly increased in comparison with the previous IPv4 protocol in which these addresses were 32 bits long. The increase in the number of fields and the increase in the number of search bits for packet classification due to the introduction of the IPv6 protocol have made it necessary in present conditions to search around 400 bits.
During the searching of the rule table, it is necessary to search through the rules (also termed entries) which are made up from this entire field information for the field which most closely resembles or agrees with the header information of the packet which is the subject. As one method for performing this type of search, the method of searching through the entire rule table from top to bottom may be considered. However, with this method, when the rules in the rule table become longer (the number of bits in each rule increases), the problem arises that a much longer time period is required for the search.
Due to this, in the past, as packet classification search methods, there have been employed the method of using a tree structure like a binary search tree, or the method of using a CAM (Content Addressable Memory), the application of which has become more common in recent years.
The problems when searching an IP address using a tree structure will be explained with reference to FIG. 22 which shows examples of tree structure. In this figure, the reference symbol 31 denotes a tree structure in the case of the IPv4 protocol, while the reference symbol 32 denotes a tree structure in the case of the IPv6 protocol; and, if these trees are used, when the search bit length becomes great as with the IPv6 protocol, the tree depth is increased by a corresponding amount, and the number of times searching must be performed increases, so that the number of times the memory is referred to increases, and the problem arises that the speed of search becomes slower. In particular, since when implementing packet classification not only the IP address but also other fields are necessary, the tree becomes longer to the same extent that the fields increase, and the problem arises that the speed of the search becomes slower.
FIG. 23 shows the outline of packet classification using a content addressable memory, and in this figure the reference symbol 41 denotes a content addressable memory, the reference symbol 42 denotes rules stored in this content addressable memory 41, and the reference symbol 43 is a search results storage memory which stores actions which correspond to these rules, while the reference symbol 44 denotes actions for search results stored in this search result storage memory 43.
The rules 42 are stored in the content addressable memory 41, and the actions 44 which correspond to the rules 42 are stored in the search result storage memory 43. The searching is performed by inputting the fields which are to be searched into the content addressable memory 41 and searching through them, and after this search, if the fields which have been inputted match any one of the rules, the search result storage memory 43 is inspected for a stored action which corresponds to the rule which has matched, and the required action is performed upon the packet.
A content addressable memory is a memory device that is not accessed with addresses as search keys, but can be accessed with the values which are recorded in its addresses as search keys, and its distinguishing characteristic is that it compares all at one time the entire set of data fields which are stored in the content addressable memory with the data fields which has been inputted and is the subject of search. In a content addressable memory ternary notation is employed, in which not only are binary values xe2x80x980xe2x80x99 and xe2x80x981xe2x80x99 stored at each address, but also some fields may be expressed as xe2x80x98don""t carexe2x80x99 which agrees with both xe2x80x980xe2x80x99 and xe2x80x981xe2x80x99. It becomes possible to perform searching of a rule table at extremely high speed by using a content addressable memory (TCAM) of this ternary type. However, the bit width which can be searched in such a content addressable memory is limited, and no content addressable memory exists at the present time in which it is possible to perform searching for around 400 bits such as has currently become necessary, as has been explained above, so that there has been the problem that it has not been possible to perform the packet classification for packets in accordance with the IPv6 protocol.
Furthermore, a TCAM or CAM memory device is different from SRAM (Static Random Access Memory) or DRAM (Dynamic Random Access Memory), in which capacity extension in the horizontal direction is not applicable. This is due to differences in the access methods for TCAMs and CAMs, as compared to those for SRAMs and DRAMs. Since SRAMs and DRAMs are accessed by addresses, when extending them in the horizontal direction, they are subdivided into a plurality of banks, and it is easily possible to implement extension in the horizontal direction by feeding in the same address signal to each memory bank.
By contrast to this, since TCAMs and CAMs are accessed by the contents which are stored in them, it is not possible to obtain the desired results, even if the contents are subdivided in the horizontal direction and are stored in a plurality of banks of TCAMs or CAMs, since no association can be established between the TCAMs or CAMs.
In recent years increase of the horizontal width of the rule table has steadily progressed, and this type of problem has become more and more manifest. For example, the horizontal width of the rule table has increased due to the advance in rules for packet classification which causes requirements for header information of higher layers, and the use of the long addresses (128 bits) of the IPv6 protocol etc. In the case of the IPv6 protocol, even with only the above described six fields, SA consists of 128 bits, DA consists of 128 bits, SP consists of 16 bits, DP consists of 16 bits, PID consists of 8 bits, and DSCP consists of 8 bits, so that the total consists of 304 bits. Furthermore, when other fields than these are also added, the width of the rule table can easily become around 400 bits, as described above.
The objective of the present invention is to solve the above described problems, and to implement a packet classification search device and method which can search through rules for packet classification whose bit width is extremely great.
In order to solve the above described problems, the packet classification search device according to the present invention is one which, based upon fields included in packets which are used to classify the flow of the packets, searches through a rule table comprising a plurality of rules which combine the fields and actions to be performed in relation to packets of which the flow is classified by the fields, and determines actions to be performed in relation to the packets, comprising: a content addressable memory which combines and stores grouped fields which have been grouped from fields included in the rules into a plurality of groups determined in advance, and number of searches information and search related information which respectively show the groups and the rules to which the grouped fields are related; a search result storage device which stores, in correspondence to the combinations which are stored in the content addressable memory, actions which are to be performed when combinations of grouped fields, number of searches information and search related information that have been inputted to the content addressable memory are found in the content addressable memory, and comparison related information which show the rules to search when next searching in the content addressable memory; and: a processing device which: extracts the fields from packets which have been inputted and generates the grouped fields; inputs into the content addressable memory and searches the number of searches information and the search related information which show the groups and rules which should be searched, and the grouped fields which correspond to the groups; obtains the actions and the comparison related information which are stored in the search result storage device in correspondence to combinations which have been searched in the content addressable memory; and, until the details of the actions which are to be performed as the actions upon the packets are obtained, again inputs to the content addressable memory the number of searches information which shows the groups which should next be searched, the grouped fields which correspond to the groups, and the comparison related information which has been obtained, and performs the searching again.
Furthermore, the packet classification search method according to the present invention is one which, based upon fields included in packets which are used to classify the flow of the packets, searches through a rule table comprising a plurality of rules which combine the fields and actions to be performed in relation to packets of which the flow is classified by the fields, and determines actions to be performed in relation to the packets, comprising the steps of: a step of providing a content addressable memory to combine and store grouped fields which have been grouped from fields included in the rules into a plurality of groups determined in advance, and number of searches information and search related information which respectively show the groups and the rules to which the grouped fields are related, and of providing a search result storage device which stores, in correspondence to the combinations which are stored in the content addressable memory, actions which are to be performed when combinations of grouped fields, number of searches information and search related information that have been inputted to the content addressable memory are found in the content addressable memory, and comparison related information which show the rules to search when next searching in the content addressable memory; a step of extracting the fields from packets which have been inputted and generating the grouped fields; a step of inputting into the content addressable memory and searching the grouped fields which correspond to the groups which are to be initially searched and number of searches information which designates the groups; a step of obtaining the actions and the comparison related information which are stored in the search result storage device in correspondence to search results which have been outputted from the content addressable memory; a step of, if the action which has been obtained shows re-searching of the content addressable memory, again inputting number of searches information which shows the groups which should next be searched, the grouped fields which correspond to the groups and search related information which has the same contents as the comparison related information which has been obtained to the content addressable memory and performing searching; and a step of, if the actions show details of actions which are to be performed upon the packets which are inputted, terminating the searching of the content addressable memory and outputting the details of the actions.
In this manner, with the present invention, the fields which are included in each rule of the original rule table are grouped into a plurality of groups and are stored in the content addressable memory, in order to store the fields in the content addressable memory of which the bit width which can be searched is limited. At this time, the number of searches information is stored together therewith, in order for each group to show in which position the original rule was located. Furthermore, the search related information is also stored together therewith, in order to show that each of those groups is related to the original rules.
When searching the content addressable memory in which the grouped rule table is stored, the content addressable memory is searched a plurality of times. The maximum number of times that the content addressable memory is searched is the number of groups of fields of rules which are included in the original rule table. Each time the content addressable memory is searched, the content addressable memory is searched with the information which is included in the header of the packet and the like, the number of searches information, and the search related information as search keys. Here, the number of searches information is information which shows which number search this one is. The comparison related information in the search result storage device which was obtained when searching in the previous round of searching is used as search related information in this round of searching. In the initial round of searching, it is arranged that this search related information matches any of the search related information which is to be the object of initial searching in the content addressable memory. In concrete terms, along with setting xe2x80x9cdon""t carexe2x80x9d to the search related information in the content addressable memory which is to be searched in the initial round of searching, it is acceptable to assign any value as the search related information which is inputted to the content addressable memory when performing the initial round of searching. Or it would also be acceptable to set the same value to all the search related information in the content addressable memory which is to be the object of searching in the initial round of searching, and to the search related information which is inputted to the content addressable memory when performing the initial round of searching.
Since with the present invention the grouped fields and the number of searches information such as the group number etc. are inputted to the content addressable memory all together when performing searching, therefore, even if the stored values relating to different groups in the content addressable memory accidentally match, it is possible to distinguish them. Furthermore, since the search related information such as the rule number etc. are inputted to the content addressable memory together with the grouped fields when searching, therefore, even if the values of the grouped fields relating to different rules which are stored in the content addressable memory accidentally match, it is possible to distinguish them.
Furthermore, with the present invention, when the results of the search result storage device have been read after searching the initial group, if it is necessary to search the next group, since its comparison related information such as its rule number etc. are stored, by again generating the search related information such as the group number and the like, when searching the next group, it is possible to input to the content addressable memory and to search these numbers together with the search object of the next group. Moreover, if it is not necessary to search the next group, then since only the required action is stored in the search result storage device, therefore it is possible to terminate the search without necessarily searching all the groups.
As described above, with the present invention, the groups of the fields of the rules which are included in the original rule table are stored in the content addressable memory, and, since a single rule comes to be grouped into a plurality of groups and to be stored in the content addressable memory, therefore it becomes possible to store a rule of bit width which is greater than the bit width which can be stored in the content addressable memory.
Accordingly it is possible to perform packet classification searching even with rules of which the width is great, and which have such a very great bit width that, in the background art, it was not possible to perform searching within the limits of a content addressable memory of which the bit width which could be searched was short. Moreover, the access time to the content addressable memory is of the order of 10 nanoseconds, and it thus becomes possible to perform searching of the rule table at an extremely high speed shorter than 32 nanoseconds, which is the time period in which it is necessary to perform searching in order to transmit 40-byte packets upon a 10 Gb/s transmission line.
According to the present invention, it is also acceptable, when grouping the fields which are included in the rules, to determine whether or not there is a possibility of a plurality of grouped fields which are related to the same group matching to specified data, and, if there is a possibility of such matching, for the grouped fields with the exception of that grouped field among the plurality of grouped fields which has the narrowest range, to generate and to insert into the rule table a new rule which has, as contents of the grouped fields for which there is the possibility of matching, the same contents as the grouped field which has the narrowest range, and moreover, as the contents of the grouped fields other than the grouped fields for which there is the possibility of matching and as the action, having the same contents as the rule to which are related the grouped fields; and to store information in the content addressable memory and in the search result storage device based upon a rule table to which the new rule has been added.
By doing this, when grouping the rule table and storing it in the content addressable memory, it is possible to prevent ambiguity from being generated between the rules by the grouping.